/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package mylist;

import exceptions.MyIndexOutOfBoundsException;
import interfaces.*;
import java.util.Iterator;


/**
 *
 * @author Daryna_Ragimova
 */
public class MyLinkedList<E> implements MyList<E>, MyStack<E> ,myQueue<E> {

    
    private static class Node<E> {
	E element;
	Node<E> next;
	Node<E> previous;

	Node(E element, Node<E> previous,Node<E> next) {
	    this.element = element;
	    this.next = next;
	    this.previous = previous;
	}
    }
    private Node<E> header = new Node<E>(null, null, null);
    private int size = 0;
    
    //in the empty linked list header links to the header
    public MyLinkedList(){
        header.next = header.previous = header;
    }
    
    public MyLinkedList(MyList c){
        this();
        addAll((E[])c.toArray());
    }

    private void remove(Node<E> e) {
        if (e != header){
            e.next.previous = e.previous;
            e.previous.next = e.next;
            e.next = null;
            e.previous = null;
            e.element = null;
            size--;
        }
    }
    
    @Override
    public void add(E e) {
        Node<E> newNode = new Node<E>(e, header.previous, header);
	newNode.previous.next = newNode;
	newNode.next.previous = newNode;
	size++;
    }

    //returns node with such index
    private Node<E> getNode(int index)  {
        if (index < 0 || index >= size)
            throw new MyIndexOutOfBoundsException("Index is not right");
        Node<E> e = header;
        if (index < (size / 2)) {
            for (int i = 0; i <= index; i++)
                e = e.next;
            
        } else {
            for (int i = size; i > index; i--)
                e = e.previous;
            
        }
        return e;
    }
    
    @Override
    public void add(int index, E element)  {
        Node<E> pointer;
        if (index == size){
            pointer = header;
        }
        pointer = getNode(index);
        Node<E> newNode = new Node<E>(element, pointer.previous, pointer);
	newNode.previous.next = newNode;
	newNode.next.previous = newNode;
	size++;
    }

    @Override
    public void addAll(E[] c) {
        addAll(size, c);
    }

    @Override
    public void addAll(int index, E[] c){
        if (index < 0 || index > size)
            throw new MyIndexOutOfBoundsException("Index is not right");
        if (c!= null){
            int quantityOfNew = c.length;
            Node<E> insertBefore;
            if (index == size){
                insertBefore = header;
            }
            else{
                insertBefore = getNode(index);
            }
            Node<E> insertAfter = insertBefore.previous;
            for (int i = 0; i < quantityOfNew; i++){
                Node<E> newNode = new Node<E>(c[i], insertAfter, insertBefore);
                newNode.previous.next = newNode;
                newNode.next.previous = newNode;
                insertAfter = newNode;
            }
            size += quantityOfNew;
        }
    }

    @Override
    public E get(int index) {
        return getNode(index).element;
    }

    @Override
    public E remove(int index) {
        Node<E> e = getNode(index);
        E result = e.element;
        e.previous.next = e.next;
        e.next.previous = e.previous;
        e.next = e.previous = null;
        e.element = null;
        size--;
        return result;
    }

    @Override
    public void clear() {
        Node<E> e = header.next;
        while (e != header) {
            Node<E> next = e.next;
            e.next = e.previous = null;
            e.element = null;
            e = next;
        }
        header.next = header.previous = header;
        size = 0;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void set(int index, E e) {
        Node<E> elem = getNode(index);
        elem.element = e;
    }

    @Override
    public int indexOf(Object o) {
        int index = 0;
        if (o==null) {
            for (Node e = header.next; e != header; e = e.next) {
                if (e.element==null)
                    return index;
                index++;
            }
        } else {
            for (Node e = header.next; e != header; e = e.next) {
                if (o.equals(e.element))
                    return index;
                index++;
            }
        }
        return -1;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public Object[] toArray() {
        Object[] result = new Object[size];
        int i = 0;
        for (Node<E> e = header.next; e != header; e = e.next)
            result[i++] = e.element;
	return result;
    }

    @Override
    public MyListIterator<E> iterator() {
        return new MyListItr(0);
    }
    @Override
    public MyListIterator<E> iterator(int index) {
        return new MyListItr(index);
    }
    @Override
    public void push(E e) {
        addFirst(e);
    }

    @Override
    public E pop() {
        return removeFirst();
    }

    @Override
    public void offer(E e) {
        add(e);
    }

    @Override
    public E peek() {
        if (size==0)
            return null;
        return getFirst();
    }

    @Override
    public E poll() {
        if (size==0)
            return null;
        return removeFirst();
    }
    public void addFirst(E e){
        Node<E> newEntry = new Node<E>(e, header.next.previous, header.next);
	newEntry.previous.next = newEntry;
	newEntry.next.previous = newEntry;
	size++;
    }
    public void addLast(E e){
        Node<E> newEntry = new Node<E>(e, header.previous, header);
	newEntry.previous.next = newEntry;
	newEntry.next.previous = newEntry;
	size++;
    }
    public E getFirst(){
        if (size == 0){
            return null;
        }
        else{
            return header.next.element;
        }
            
    }
    public E getLast(){
        if (size == 0){
            return null;
        }
        else{
            return header.previous.element;
        }
    }
    public E removeFirst(){
        if (size == 0){
            return null;
        }
        else{
            Node<E> e = header.next;
            E elem = e.element;
            header.next = e.next;
            e.element = null;
            e.next = null;
            e.previous = null;
            size--;
            return elem;
        }
    }
    public E removeLast(){
        if (size == 0){
            return null;
        }
        else{
            Node<E> e = header.previous;
            E elem = e.element;
            header.previous = e.previous;
            e.element = null;
            e.next = null;
            e.previous = null;
            size--;
            return elem;
        }
    }
    public Iterator<E> descendingIterator() {
        return new DescendingIterator();
    }
    private class MyListItr implements MyListIterator<E> {
        private Node<E> lastReturned = header;
        private Node<E> next;
        private int nextIndex;
        
        MyListItr(int index) {
            if (index < 0 || index > size)
                throw new IndexOutOfBoundsException("Index is not right");
            if (index < (size >> 1)) {
                next = header.next;
                for (nextIndex=0; nextIndex<index; nextIndex++)
                    next = next.next;
            } else {
                next = header;
                for (nextIndex=size; nextIndex>index; nextIndex--)
                    next = next.previous;
            }
        }

        @Override
        public boolean hasNext() {
            return nextIndex != size;
        }

        @Override
        public E next() {
            if (nextIndex == size)
                return null;

            lastReturned = next;
            next = next.next;
            nextIndex++;
            return lastReturned.element;
        }

        @Override
        public boolean hasPrevious() {
            return nextIndex != 0;
        }

        @Override
        public E previous() {
            if (nextIndex == 0)
                return null;
            next = next.previous;
            lastReturned = next;
            
            nextIndex--;
            return lastReturned.element;
        }

        @Override
        public void remove() {
            MyLinkedList.this.remove(lastReturned);
            nextIndex--;
            lastReturned = header;
        }

        @Override
        public int nextIndex() {
            return nextIndex;
        }

               
        @Override
        public void set(E e) {
            if (lastReturned == null)
                throw new IllegalStateException();
            lastReturned.element = e;
        }

        @Override
        public void add(E e) {
            lastReturned = header;
            MyLinkedList.this.add(e);
            nextIndex++;
        }
    }
 

    private class DescendingIterator implements Iterator<E> {
        final MyListItr iterator = new MyListItr(size());
        @Override
	public boolean hasNext() {
	    return iterator.hasPrevious();
	}
        @Override
	public E next() {
            return iterator.previous();
        }
        @Override
	public void remove() {
            iterator.remove();
        }
    }
}
